1. Field of the Invention
The present invention relates to a content addressable memory device and a method of disabling a coincidence word. More particularly, the present invention relates to a content addressable memory (CAM) conducting a retrieval operation on the basis of an applied retrieval data and designation of a particular word, and to a method of disabling a coincidence word thereof.
2. Description of the Background Art
FIG. 21 is a block diagram showing a whole structure of a cache system employing a conventional CAM. In FIG. 21, a main memory 101 and a cache memory 103 are connected to a CPU 106 through a data bus 104 and an address bus 105. A dynamic RAM or a magnetic disk device is used as main memory 101. The magnetic disk device has relatively slow access time but has large storage capacity, and it is inexpensive. A CAM is used as cache memory 103. Though the storage capacity of CAM is small, it allows speedy access. Cache memory 103 is used to reduce access time of the main memory 101. Among the data stored in main memory 101, data which are frequently accessed are stored together with their addresses, in the cache memory 103. Writing and comparing operation in cache memory 103 is carried out under the control of a memory controller 102.
In the cache system structured as described above, cache memory 103 is accessed prior to the access to main memory 101 by CPU 106. More specifically, when an address signal is output from CPU 106 to address bus 105, cache memory 103 is controlled by a memory controller 102, and whether or not the address corresponding to the address signal is stored in cache memory 103 is determined. When the corresponding address has been stored in cache memory 103, a hit signal is provided from cache memory 103 and applied to memory controller 102. When the hit signal is applied from memory controller 102 to CPU 106, data in that region which corresponds to the region storing the address in cache memory 103 is read. When there is no address corresponding to the address signal output from the CPU 106 stored in cache memory 103, the hit signal is not applied and the main memory 101 is accessed.
The above described cache memory 103 includes a plurality of content addressable memory cells (hereinafter referred to as CAM cells). The CAM cell has, in addition to the normal writing and reading functions, a coincidence retrieval function in which data stored in the memory cell is compared with a retrieval data applied externally and whether or not they match with each other is detected.
Different from the normal memory, the basic function of a CAM is to enter a reference data and output an address of the word where the data matches with the reference data is stored. Generally, in a retrieval operation of the CAM, not all of the words in the memory array participate in the coincidence retrieving operation. Namely, there are unnecessary words which are not subjected to retrieval in the memory array of the CAM. Management of such unnecessary words is referred to as a garbage collection.
Conventionally, a flag bit has been provided corresponding to each word for performing the garbage collection. More specifically, when the flag bit is "0", the corresponding word participates in the coincidence retrieval, and when the flag is "1", the corresponding word does not participate in the coincidence retrieval. A register used only as the flag bit may be provided corresponding to each word, as a flag bit. However, in order to simplify the structure of the CAM, method employing CAM cells constituting a memory array as flag bits have been also proposed. The following prior art example of interest is one of such methods.
FIG. 22 is a block diagram showing an example of a CAM disclosed in Japanese Patent Laying-Open No. 1-223697 (U.S. Pat. No. 4,975,873). Referring to FIG. 22, the CAM includes a memory cell array 2, a read/write control portion 1, a flag bit column 12 and a flag bit control portion 11. Memory cell array 2 carries out reading and writing of data. Read/write control portion 1 inputs/outputs data and retrieval data to and from memory cell array 2 through bit line pairs B0 to Bn-1 with the timing controlled. Flag bit column 12 is coupled to memory cell array 2 and stores flag signals indicating the state of writing of each word. Flag bit control portion 11 is coupled to read/write control portion 1 and inputs/outputs to and from the flag bit column 12, flag signals of which timings are controlled through a bit line pair Bn.
The CAM further includes a response register 3, a multi-selection separating circuit 4, a word control circuit 6 and a control circuit 5. Response register 3 temporarily holds a result of retrieval output from flag bit column 12 and memory cell array 2. Multi-selection separating circuit 4 selects, when a plurality of results of retrieval are obtained, one of these results in accordance with a predetermined logic and outputs a match address MA thereof. Word control circuit 6 receives an external address EA, the match address MA and a control signal .phi.5 from control circuit 5, and drives and controls word lines W0 to Wm-1 and match lines M0 to Mm-1. Control circuit 5 provides timing control signals .phi.1 to .phi.5.
In the CAM shown in FIG. 22, when flag bit control portion 11 and read/write control portion 1 are set in accordance with control signal .phi.1 and external data D0 to Dn, reading, writing and coincidence retrieval operations in both the flag bit column 12 and the memory cell array 2 can be simultaneously carried out by a control signal .phi.2, without any specific complicated control. These operations will be described in the following.
In the coincidence retrieval operation, a retrieval data is set in flag bit control portion 11 and in read/write control portion 1 in a retrieval mode; a control signal .phi.5 is applied to word control circuit 6 to set match lines M0 to Mm-1 at set potentials; the retrieval data is applied to memory cell array 2 and the flag bit column 12; then results of retrieval provided to match lines M0 to Mm-1 are latched in response register 3 and input to the multi-selection separating circuit 4, so that the results are output as match addresses MA, and thus the operation is completed. A restricting retrieval (mask retrieval) is available by masking the retrieval data.
In writing operation, a write data is set in flag bit control portion 11 and read/write control portion 1 in a write mode; the write data is applied to memory cell array 2 and flag bit column 12; a word to be written is selected by applying the control signal .phi.5 and the external address EA of word control circuit 6; and the write data is written to the word, thus completing the operation. Partial writing (mask writing) is also possible by masking the write data.
In reading operation, a word from which reading is to be done is selected by inputting the control signal .phi.5 and the external address EA to word line control circuit 6 in a read mode, and read data from the selected word is taken in flag bit control portion 11 and read/write control portion 1.
The retrieval of unnecessary words (garbage collection) is effected by masking the memory cell array 2 by using mask data in the retrieval mode, and mask retrieval is effected only to flag bit column 12. The results of retrieval output to match lines M0 to Mm-1 are input to response register 3 and multi-selection separating circuit 4. Multi-selection separating circuit 4 outputs match address MA indicating the unnecessary word, the match address MA is input to word control circuit 6, and thus the operation is completed. More specifically, by the provision of the flag bit column 12, garbage collection is implemented in a simple manner. One of the unnecessary words may be activated by inputting the match address to word control circuit 6, so that data can be newly written to the unnecessary word in the subsequent write mode.
FIG. 23 is a schematic diagram showing an example of the flag bit column and the memory cell array shown in FIG. 22. Referring to FIG. 23, flag bit column 12 includes flag cells Cn, 0 to Cn, m-1 respectively connected to bit lines bn and/bn, word lines W0 to Wm-1 and match lines M0 to Mm-1.
Memory cell array 2 includes CAM cells C0, 0 to Cm-1, n-1 respectively connected to bit lines b0 and/b0 to bn-1 and/bn-1, word lines W0 to Wm-1 and match lines M0 to Mm-1.
As is apparent from FIG. 23, the flag cell used in flag bit column 12 and the CAM cell used in memory cell array 2 have identical structure. Further, word lines W0 to Wm-1 and match lines M0 to Mm-1 are used commonly in the flag bit column 12 and memory cell array 2. Therefore, special control signal for the flag bit column 12 is not necessary.
As described above, in the prior art example, garbage collection can be implemented without adding any complicated control means, since CAM cells are commonly used in flag bit column 12 and memory cell array 2.
FIG. 24 shows a principle of data retrieval in the CAM shown in FIG. 22. Referring to FIG. 24, when coincidence retrieval data "1011xxx" (xxx denote Don't Care: bits which are not the object of retrieval) is input from read/write control portion 1, CAM 2 retrieves data which coincides with the higher 4 bits "1011" of the coincidence retrieval data, determines whether or not the data of the third word W3, the sixth word W6 and the tenth word W10 coincide, and transfer "1" to the corresponding word in response register 3. Multi-selection separating circuit 4 contains a priority encoder 41 and a register 42. Priority encoder 41 has priorities of respective rows set therein. When three pieces of data coincide with the coincidence retrieval data as described above, "1" is set at a bit of a register 42 corresponding to that word which has the highest priority.
FIG. 25 (a) shows the concept of comparison between the data including a flag bit and the coincidence retrieval data including a flag bit. In the example shown in FIG. 25 (a), "0" in the coincidence retrieval data "abc0" indicates the flag bit. Among the data stored in CAM2, data which has "1" as the flag bit does not participate in retrieval and only that data of which flag bit is "0" participates the retrieval. In this example, the data of the second word W2 coincides with the coincidence retrieval data, and therefore "1" is set in response register 3 corresponding to the data of the second word W2. When there are plural data which coincide, "1" is set in response register 3 corresponding to the data having the highest priority, in the same manner as described with reference to FIG. 24.
FIG. 25 (b) shows the concept of mask retrieval. Among the coincidence retrieval data, word data are masked, and masked word data are all regarded as coincident. Therefore, retrieval is carried out only by the flag bit. The coincidence retrieval data with the flag bit only is successively compared with the flag bit of the CAM memory cell array 2, and "1" is set at the corresponding word of the response register 3 of which flag bit coincides.
There may be the case where an operation of disabling all of the plurality of coincident words is necessary. More specifically, in coincidence retrieval, when coincidence of one word is retrieved, retrieval may no longer be required. In that case, the plurality of coincident words must be disabled. To carry out this operation in the CAM shown in FIG. 22, the content of response register 3 is input to multi-selection separating circuit 4, one of the addresses of the coincidence word is input to word control circuit 6 and the word is activated. Then, by the control of flag bit control portion 11, the flag bit of that word is changed from "0" to "1". Then, the value of response register 3 corresponding to that word is rewritten from "1" (coincidence) to "0" (non-coincidence). By the above described operation, disabling of one word among a plurality of words is completed. Therefore, in order to disable a plurality of coincident words, the above described operation of coincidence must be repeated for the number of times corresponding to the number of coincident words.
On the contrary, there may be a case where an operation of disabling all the non-coincident words is necessary. In that case also, the operation similar to that of disabling all coincident words described above must be repeated.
Since the number of words is large in a CAM having large storage capacity, there may be a large number of words which are coincident. Therefore, much time is consumed to operate all the coincident words in accordance with the above described manner.